package com.cat.dataStructure02;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/remove-k-balanced-substrings/
 * @create 2025/10/26 13:20
 * @since JDK17
 */

public class Solution59 {
    public String removeSubstring(String s, int k) {
        List<int[]> stack = new ArrayList<>();
        StringBuilder ans = new StringBuilder();
        for (var c : s.toCharArray()) {
            int size = stack.size();
            if (size == 0 || stack.get(size - 1)[0] != c) {
                stack.add(new int[]{c, 1});
                size++;
            } else {
                stack.get(size - 1)[1]++;
            }
            if (c == ')' && size > 1 && stack.get(size - 1)[1] >= k && stack.get(size - 2)[1] >= k) {
                stack.remove(size - 1);
                int[] last = stack.get(size - 2);
                last[1] -= k;
                if (last[1] == 0) {
                    stack.remove(size - 2);
                }
            }
        }
        for (var cur : stack) {
            ans.append(String.valueOf((char) cur[0]).repeat(cur[1]));
        }

        return ans.toString();
    }
}
